package lc2;
import java.util.*;
import org.junit.*;

import util.TreeNode;
import util.TreeUtils;
public class Ex144 {
    
class Solution {

    //mirrors前序遍历
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        TreeNode cur = root;
        while (cur != null) {
            res.add(cur.val);
            if (cur.left != null) {
                TreeNode last = findLast(cur);
                if (last.right != cur) {
                    //没有遍历过
                    last.right = cur;
                    cur = cur.left;
                } else {
                    //已经遍历过了
                    last.right = null;
                    cur = cur.right;
                }
            } else {
                cur = cur.right;
            }
        }
        return res;
    }

    private TreeNode findLast(TreeNode root) {
        TreeNode pre = null, cur = root.left;
        while (cur != null && cur.right != root) {
            pre = root;
            cur = cur.right;
        }
        return pre;
    }


}

    @Test
    public void test() {
        Solution s = new Solution();
        Integer[] is = new Integer[]{1,null,2,3};
        System.out.println(s.preorderTraversal(TreeUtils.createTree(is)));
    }
}
